/*
公共头文件, 定义了一些需要使用的结构 以及 一些条件编译处理
*/
#pragma once
#include <iostream>
#include <cassert>
#include <vector>
#include <ctime>
#include <chrono>
#include <thread>
#include <mutex>
#include <unordered_map>
using std::cin;
using std::cout;
using std::endl;
#define NFREELIST 208
#define MAXBYTES 256*1024
#define NPAGES 129

//---------------------条件编译开始---------------------
#ifdef _WIN32
    #define NOMINMAX
    #include <windows.h>
    inline size_t GetPageSize() {
        SYSTEM_INFO sys_info;
        GetSystemInfo(&sys_info);
        return sys_info.dwPageSize;
    }
    static const size_t PAGE_SIZE = GetPageSize();  // 动态初始化系统页大小
    #if defined(_WIN64)
        // 64位 Windows 专用代码
        typedef unsigned long long PAGE_ID;
    #else
        // 32位 Windows 专用代码
        typedef size_t PAGE_ID;
    #endif
#else  //__linux__
    #include <sys/mman.h>
    #include <unistd.h>
    static const size_t PAGE_SIZE = sysconf(_SC_PAGESIZE); // 获取系统页大小(全局静态的)
    #if defined __x86_64__
        // 64位 Linux 专用代码
        typedef unsigned long long PAGE_ID;//页号类型
    #else
        // 32位 Linux 专用代码
        typedef size_t PAGE_ID;//页号类型
    #endif
#endif

//条件编译 windows / linux 下直接从堆 分配/释放 空间的系统接口
inline void* SystemAlloc(const size_t& kpage) {
#ifdef _WIN32
    //windows下
    void* ptr = VirtualAlloc(0, kpage * PAGE_SIZE, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
    //linux下
    void* ptr = mmap(nullptr, kpage * PAGE_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
#endif
    assert(ptr);
    return ptr;
}

inline void SystemFree(void* ptr, const size_t& kpage) {
#ifdef _WIN32
    //windows下
    VirtualFree(ptr, 0, MEM_RELEASE);
#else
    //linux下
    munmap(ptr, kpage * PAGE_SIZE);
#endif
}
//---------------------条件编译结束---------------------

//计算对象大小的对齐映射规则
class SizeMapClass {
    // 整体控制在最多10%左右的内碎片浪费
    // [1,128]               8byte对齐          freelist[0,16)
    // [128+1,1024]          16byte对齐         freelist[16,72)
    // [1024+1,8*1024]       128byte对齐        freelist[72,128)
    // [8*1024+1,64*1024]    1024byte对齐       freelist[128,184)
    // [64*1024+1,256*1024]  8*1024byte对齐     freelist[184,208)
private:
    static inline size_t RoundUp_(size_t size, size_t align) {
        return ((size + align - 1) & (~(align - 1)));
    }
    static size_t Index_(size_t size, size_t align_shift) {
        return ((size + (1 << align_shift) - 1) >> align_shift) - 1;
    }
public:
    //根据空间size 计算对齐后的大小
    static inline size_t RoundUp(size_t size) {
        if (size <= 128)               return RoundUp_(size, 8);
        else if (size <= 1024)         return RoundUp_(size, 16);
        else if (size <= 8 * 1024)     return RoundUp_(size, 128);
        else if (size <= 64 * 1024)    return RoundUp_(size, 1024);
        else if (size <= 256 * 1024)   return RoundUp_(size, 8 * 1024);
        else {
            return RoundUp_(size, PAGE_SIZE);//按页对齐,不走三层缓存
        }
    }

    //根据空间size 计算哈希桶
    static size_t Index(size_t size) {
        static int group_array[4] = { 16,72,128,184 };
        if (size <= 128)               return Index_(size, 3);
        else if (size <= 1024)         return Index_(size - 128, 4) + group_array[0];
        else if (size <= 8 * 1024)     return Index_(size - 1024, 7) + group_array[1];
        else if (size <= 64 * 1024)    return Index_(size - 8 * 1024, 10) + group_array[2];
        else if (size <= 256 * 1024)   return Index_(size - 64 * 1024, 13) + group_array[3];
        else {
            //错误处理, ThreadCach最多只有256K
            assert(false);
            return -1;
        }
    }

    //thread cach 一次从 Central cach 获取多少个size大小的内存块
    static size_t NumMoveSize(size_t size) {
        //f(size==0) return 0;
        assert(size > 0);
        size_t num = MAXBYTES / size;
        num = num < 2 ? 2 : num;
        num = num > 512 ? 512 : num;
        return num;
    }

    //计算一次向PageCach取几个页
    static size_t NumMovePage(size_t size) {
        size_t num = NumMoveSize(size);
        size_t npage = num * size / PAGE_SIZE;
        if (npage == 0) npage = 1;
        return npage;
    }
};

//取某个小块内存的前4/8个字节,根据系统决定
inline void*& NextPtr(void* ptr) {
    return *(void**)ptr;
}

//自由链表类
class FreeList {
public:
    void Push(void* ptr) {
        //头插
        NextPtr(ptr) = freelist_;
        freelist_ = ptr;
        ++size_;
    }
    void PushRange(void* start, void* end, size_t n) {
        NextPtr(end) = freelist_;
        freelist_ = start;
        size_ += n;
    }
    void PopRange(void*& start, void*& end, size_t n) {
        assert(n <= size_);
        start = freelist_;
        end   = freelist_;
        for (int i = 1; i < n; ++i) {
            end = NextPtr(end);
        }
        freelist_ = NextPtr(end);
        NextPtr(end) = nullptr;
        size_ -= n;
    }
    void* Pop() {
        //头删
        assert(freelist_);
        void* ptr = freelist_;
        freelist_ = NextPtr(freelist_);
        --size_;
        return ptr;
    }
    bool Empty() {
        return freelist_ == nullptr;
    }
    size_t& MaxSize() {
        return MaxSize_;
    }
    const size_t& Size() {
        return size_;
    }
private:
    void* freelist_ = nullptr;
    size_t MaxSize_ = 1;
    size_t size_ = 0;//空闲内存块计数,方便还给CentralCach
};

class Span {
public:
    PAGE_ID pageId_ = 0;//内存起始页页号
    size_t  n_ = 0;//页的数量
    Span*   next_ = nullptr;//双向链表指针
    Span*   prev_ = nullptr;//双向链表指针
    size_t  useCount_ = 0;//切好的内存 被使用计数, =0说明这个span内存全部还回来了
    size_t  objSize_  = 0;//切好的对象占几个字节
    bool    isUse_ = false;//是否在被Central Cach使用
    void*   freelist_ = nullptr;//切好的内存的自由链表
};

//Span双向链表结构
class SpanList {
public:
    SpanList() {
        head_ = new Span;
        head_->next_ = head_;
        head_->prev_ = head_;
    }
    //插入span节点
    void Insert(Span* pos, Span* newSpan) {
        assert(pos);
        assert(newSpan);
        newSpan->next_ = pos;
        newSpan->prev_ = pos->prev_;
        pos->prev_->next_ = newSpan;
        pos->prev_ = newSpan;
    }
    //删除span节点
    Span* Erase(Span* pos) {
        assert(pos);
        assert(pos != head_);
        pos->prev_->next_ = pos->next_;
        pos->next_->prev_ = pos->prev_;
        pos->prev_ = pos->next_ = nullptr;
        return pos;
    }
    //伪迭代器
    Span* Begin() {
        return head_->next_;
    }
    Span* End() {
        return head_;
    }

    bool Empty() {
        return head_->next_ == head_;
    }
    //头插头删span节点
    void Push(Span* newSpan) {
        Insert(this->Begin(), newSpan);
    }
    Span* Pop() {
        return Erase(this->Begin());
    }
    //锁住当前Span链表
    void Lock() {
        mtx_.lock();
    }
    //解锁当前Span链表
    void UnLock() {
        mtx_.unlock();
    }
private:
    Span* head_;//哨兵/头 节点
    std::mutex mtx_;//每个SpanList都有的一个互斥锁
};